#include <iostream>
using namespace std;

// 对于相似的问题，可以采用函数指针增加可扩展性

// 1.调整数组顺序使得奇数在前，偶数在后
bool isEven(int n)
{
    return (n & 1) == 0;
}

// 2. 负数在前，非负数在后
bool isNegative(int n)
{
    return n >= 0;
}

// 3. 能被三整除的在前，不能被三整除的在后
bool isDevidedBy3(int n)
{
    return (n % 3) != 0;
}

void ReOrderArray(int * pData, unsigned int length, bool (*func)(int)) // 函数指针
{
    if (NULL == pData || length <= 0)
        return;

    int *pBegin = pData;
    int *pEnd = pData + length - 1;

    while (pBegin < pEnd)
    {   
        // 向后移动pBegin直到指向偶数
        while (pBegin < pEnd && !func(*pBegin))
            pBegin ++;
        // pEnd向前移动，直到遇到奇数
        while (pBegin < pEnd && func(*pEnd))
            pEnd --;

        // Swap *pBegin with *pEnd
        if (pBegin < pEnd)
        {
            int temp = *pBegin;
            *pBegin = *pEnd;
            *pEnd = temp;
        }
    }
}

int main(int argc, char * argv[])
{
    int array[] = {3, 4, 1, -2, 5, 6, 7, 3};
    int length = sizeof(array) / sizeof(int);
    ReOrderArray(array, length, isDevidedBy3);
    for(int i = 0; i < length; ++i)
    {
        cout << array[i] << " ";
    }
    cout << endl;
    return 0;
}
